package sortalg

import "fmt"

/**
小顶堆排序
*/
/**
核心思想：
调整父节点时，必须保证两个子树已为小顶堆，才能保证调整完成后，整个树为小顶堆
 */
type SmallHeapSort struct {
	keyList []int
}

func NewSmallHeapSort(sourceList []int) *SmallHeapSort {
	qs := &SmallHeapSort{
		keyList: sourceList,
	}

	//todo 为方便数组的下标运算
	//0号位存储元素的个数
	l := []int{len(sourceList)}
	qs.keyList = append(l, sourceList...)

	qs.insertSort()

	return qs
}

func (qs *SmallHeapSort) insertSort() {
	if qs.keyList[0] <= 1 {
		return
	}

	//调整为顶堆
	length := qs.keyList[0]
	for i := length / 2; i >= 1; i-- {
		qs.heapAdjust(i, length)
	}

	//交换1号位元素
	//调整1号位的顶堆
	for i := length; i >= 1; i-- {
		qs.swap(1, i)
		qs.heapAdjust(1, i-1)
	}
}

func (qs *SmallHeapSort) heapAdjust(currentAdjustPlace, size int) {
	minValue := qs.keyList[currentAdjustPlace]
	for j := currentAdjustPlace * 2; j <= size; j *= 2 {
		if j+1 <= size && qs.keyList[j+1] < qs.keyList[j] {
			j++
		}

		if minValue > qs.keyList[j] {
			qs.keyList[currentAdjustPlace] = qs.keyList[j]
			qs.keyList[j] = minValue

			currentAdjustPlace = j
			minValue = qs.keyList[currentAdjustPlace]
		}
	}
}

func (qs *SmallHeapSort) swap(p1, p2 int) {
	tmp := qs.keyList[p1]
	qs.keyList[p1] = qs.keyList[p2]
	qs.keyList[p2] = tmp
}

func (qs *SmallHeapSort) Print() {
	fmt.Println(qs.keyList[1:])
}
